#define  _CRT_SECURE_NO_WARNINGS
#include "BinaryTree.h"

BTNode* GetNode(BTDataType x)
{
	BTNode* tmp = (BTNode*)malloc(sizeof(BTNode));
	if (!tmp)
	{
		perror("GetNode::malloc::");
		return NULL;
	}
	tmp->_data = x;
	tmp->_left = tmp->_right = NULL;
}

BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	assert(a);
	if (*pi >= n || a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
	else
	{
		BTNode* tmp = GetNode(a[*pi]);
		(*pi)++;
		tmp->_left = BinaryTreeCreate(a, n, pi);
		tmp->_right = BinaryTreeCreate(a, n, pi);
		return tmp;
	}
}

void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)return;
	BinaryTreeDestory(&((*root)->_left));
	BinaryTreeDestory(&((*root)->_right));
	free(*root);
	*root = NULL;
	return;
}

int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)return 0;
	int left = BinaryTreeSize(root->_left);
	int right = BinaryTreeSize(root->_right);
	return 1 + left + right;
}

int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)return 0;
	int count = 0;
	if (root->_left == NULL && root->_right == NULL)count++;
	int left = BinaryTreeLeafSize(root->_left);
	int right = BinaryTreeLeafSize(root->_right);
	return count + left + right;
}

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL || k == 0)return 0;
	if (k == 1)return 1;
	int left = BinaryTreeLevelKSize(root->_left,k - 1);
	int right = BinaryTreeLevelKSize(root->_right,k - 1);
	return left + right;
}

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL) return NULL;
	if (root->_data == x)return root;
	else
	{
		BTNode* left = BinaryTreeFind(root->_left, x);
		BTNode* right = BinaryTreeFind(root->_right, x);
		if (left)return left;
		return right;
	}
}

void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}
	printf("%c ", root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}

void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}
	BinaryTreePrevOrder(root->_left);
	printf("%c ", root->_data);
	BinaryTreePrevOrder(root->_right);
}

void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
	printf("%c ", root->_data);
}



/////////////////////////////////////////////////////////////

typedef BTNode* QDatatype;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDatatype data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
}

void QueuePush(Queue* pq, QDatatype x)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (!newnode)
	{
		perror("QueuePush::malloc");
		return;
	}
	newnode->next = NULL;
	newnode->data = x;

	if (!QueueEmpty(pq))
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	else
		pq->head = pq->tail = newnode;

	pq->size++;
}

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	QNode* next = pq->head->next;
	free(pq->head);
	pq->head = next;
	if (pq->head == NULL)
		pq->tail = NULL;
	pq->size--;
}

QDatatype QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

//////////////////////////////////////////////////////////////

void BinaryTreeLevelOrder(BTNode* root)
{
	Queue queue;
	QueueInit(&queue);
	if (root == NULL)
	{
		printf("#\n");
		return;
	}
	printf("%c ", root->_data);
	QueuePush(&queue, root->_left);
	QueuePush(&queue, root->_right);
	while (!QueueEmpty(&queue))
	{
		BTNode* tmp = QueueFront(&queue);
		QueuePop(&queue);
		if (tmp == NULL)
		{
			printf("# ");
		}
		else
		{
			printf("%c ", tmp->_data);
			QueuePush(&queue, tmp->_left);
			QueuePush(&queue, tmp->_right);
		}
	}
}

int BinaryTreeComplete(BTNode* root)
{
	Queue queue;
	QueueInit(&queue);
	if (root == NULL)
	{
		return 1;
	}
	QueuePush(&queue, root->_left);
	QueuePush(&queue, root->_right);
	while (!QueueEmpty(&queue))
	{
		BTNode* tmp = QueueFront(&queue);
		QueuePop(&queue);
		if (tmp == NULL)
		{
			while (!QueueEmpty(&queue))
			{
				if (QueueFront(&queue) != NULL)
				{
					return 0;
				}
				QueuePop(&queue);
			}
		}
		else
		{
			QueuePush(&queue, tmp->_left);
			QueuePush(&queue, tmp->_right);
		}
	}
	return 1;
}